import os
import json
from collections import defaultdict
seeds = [[],[3],
[7],
[11, 13],
[19, 25],
[37, 41, 47, 55, 59, 61],
[67, 91, 97, 103, 109, 115],
[131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253],
[285, 299, 301, 333, 351, 355, 357, 361, 369, 391, 397, 425, 451, 463, 487, 501],
[529, 539, 545, 557, 563, 601, 607, 617, 623, 631, 637, 647, 661, 675, 677, 687, 695, 701, 719, 721, 731, 757, 761, 787, 789, 799, 803, 817, 827, 847, 859, 865, 875, 877, 883, 895, 901, 911, 949, 953, 967, 971, 973, 981, 985, 995, 1001, 1019],
[1033, 1051, 1063, 1069, 1125, 1135, 1153, 1163, 1221, 1239, 1255, 1267, 1279, 1293, 1305, 1315, 1329, 1341, 1347, 1367, 1387, 1413, 1423, 1431, 1441, 1479, 1509, 1527, 1531, 1555, 1557, 1573, 1591, 1603, 1615, 1627, 1657, 1663, 1673, 1717, 1729, 1747, 1759, 1789, 1815, 1821, 1825, 1849, 1863, 1869, 1877, 1881, 1891, 1917, 1933, 1939, 1969, 2011, 2035, 2041],
[2053, 2071, 2091, 2093, 2119, 2147, 2149, 2161, 2171, 2189, 2197, 2207, 2217, 2225, 2255, 2257, 2273, 2279, 2283, 2293, 2317, 2323, 2341, 2345, 2363, 2365, 2373, 2377, 2385, 2395, 2419, 2421, 2431, 2435, 2447, 2475, 2477, 2489, 2503, 2521, 2533, 2551, 2561, 2567, 2579, 2581, 2601, 2633, 2657, 2669, 2681, 2687, 2693, 2705, 2717, 2727, 2731, 2739, 2741, 2773, 2783, 2793, 2799, 2801, 2811, 2819, 2825, 2833, 2867, 2879, 2881, 2891, 2905, 2911, 2917, 2927, 2941, 2951, 2955, 2963, 2965, 2991, 2999, 3005, 3017, 3035, 3037, 3047, 3053, 3083, 3085, 3097, 3103, 3159, 3169, 3179, 3187, 3205, 3209, 3223, 3227, 3229, 3251, 3263, 3271, 3277, 3283, 3285, 3299, 3305, 3319, 3331, 3343, 3357, 3367, 3373, 3393, 3399, 3413, 3417, 3427, 3439, 3441, 3475, 3487, 3497, 3515, 3517, 3529, 3543, 3547, 3553, 3559, 3573, 3589, 3613, 3617, 3623, 3627, 3635, 3641, 3655, 3659, 3669, 3679, 3697, 3707, 3709, 3713, 3731, 3743, 3747, 3771, 3791, 3805, 3827, 3833, 3851, 3865, 3889, 3895, 3933, 3947, 3949, 3957, 3971, 3985, 3991, 3995, 4007, 4013, 4021, 4045, 4051, 4069, 4073],
[4179, 4201, 4219, 4221, 4249, 4305, 4331, 4359, 4383, 4387, 4411, 4431, 4439, 4449, 4459, 4485, 4531, 4569, 4575, 4621, 4663, 4669, 4711, 4723, 4735, 4793, 4801, 4811, 4879, 4893, 4897, 4921, 4927, 4941, 4977, 5017, 5027, 5033, 5127, 5169, 5175, 5199, 5213, 5223, 5237, 5287, 5293, 5331, 5391, 5405, 5453, 5523, 5573, 5591, 5597, 5611, 5641, 5703, 5717, 5721, 5797, 5821, 5909, 5913, 5955, 5957, 6005, 6025, 6061, 6067, 6079, 6081, 6231, 6237, 6289, 6295, 6329, 6383, 6427, 6453, 6465, 6501, 6523, 6539, 6577, 6589, 6601, 6607, 6631, 6683, 6699, 6707, 6761, 6795, 6865, 6881, 6901, 6923, 6931, 6943, 6999, 7057, 7079, 7103, 7105, 7123, 7173, 7185, 7191, 7207, 7245, 7303, 7327, 7333, 7355, 7365, 7369, 7375, 7411, 7431, 7459, 7491, 7505, 7515, 7541, 7557, 7561, 7701, 7705, 7727, 7749, 7761, 7783, 7795, 7823, 7907, 7953, 7963, 7975, 8049, 8089, 8123, 8125, 8137],
[8219, 8231, 8245, 8275, 8293, 8303, 8331, 8333, 8351, 8357, 8367, 8379, 8381, 8387, 8393, 8417, 8435, 8461, 8469, 8489, 8495, 8507, 8515, 8551, 8555, 8569, 8585, 8599, 8605, 8639, 8641, 8647, 8653, 8671, 8675, 8689, 8699, 8729, 8741, 8759, 8765, 8771, 8795, 8797, 8825, 8831, 8841, 8855, 8859, 8883, 8895, 8909, 8943, 8951, 8955, 8965, 8999, 9003, 9031, 9045, 9049, 9071, 9073, 9085, 9095, 9101, 9109, 9123, 9129, 9137, 9143, 9147, 9185, 9197, 9209, 9227, 9235, 9247, 9253, 9257, 9277, 9297, 9303, 9313, 9325, 9343, 9347, 9371, 9373, 9397, 9407, 9409, 9415, 9419, 9443, 9481, 9495, 9501, 9505, 9517, 9529, 9555, 9557, 9571, 9585, 9591, 9607, 9611, 9621, 9625, 9631, 9647, 9661, 9669, 9679, 9687, 9707, 9731, 9733, 9745, 9773, 9791, 9803, 9811, 9817, 9833, 9847, 9851, 9863, 9875, 9881, 9905, 9911, 9917, 9923, 9963, 9973, 10003, 10025, 10043, 10063, 10071, 10077, 10091, 10099, 10105, 10115, 10129, 10145, 10169, 10183, 10187, 10207, 10223, 10225, 10247, 10265, 10271, 10275, 10289, 10299, 10301, 10309, 10343, 10357, 10373, 10411, 10413, 10431, 10445, 10453, 10463, 10467, 10473, 10491, 10505, 10511, 10513, 10523, 10539, 10549, 10559, 10561, 10571, 10581, 10615, 10621, 10625, 10643, 10655, 10671, 10679, 10685, 10691, 10711, 10739, 10741, 10755, 10767, 10781, 10785, 10803, 10805, 10829, 10857, 10863, 10865, 10875, 10877, 10917, 10921, 10929, 10949, 10967, 10971, 10987, 10995, 11009, 11029, 11043, 11045, 11055, 11063, 11075, 11081, 11117, 11135, 11141, 11159, 11163, 11181, 11187, 11225, 11237, 11261, 11279, 11297, 11307, 11309, 11327, 11329, 11341, 11377, 11403, 11405, 11413, 11427, 11439, 11453, 11461, 11473, 11479, 11489, 11495, 11499, 11533, 11545, 11561, 11567, 11575, 11579, 11589, 11611, 11623, 11637, 11657, 11663, 11687, 11691, 11701, 11747, 11761, 11773, 11783, 11795, 11797, 11817, 11849, 11855, 11867, 11869, 11873, 11883, 11919, 11921, 11927, 11933, 11947, 11955, 11961, 11999, 12027, 12029, 12037, 12041, 12049, 12055, 12095, 12097, 12107, 12109, 12121, 12127, 12133, 12137, 12181, 12197, 12207, 12209, 12239, 12253, 12263, 12269, 12277, 12287, 12295, 12309, 12313, 12335, 12361, 12367, 12391, 12409, 12415, 12433, 12449, 12469, 12479, 12481, 12499, 12505, 12517, 12527, 12549, 12559, 12597, 12615, 12621, 12639, 12643, 12657, 12667, 12707, 12713, 12727, 12741, 12745, 12763, 12769, 12779, 12781, 12787, 12799, 12809, 12815, 12829, 12839, 12857, 12875, 12883, 12889, 12901, 12929, 12947, 12953, 12959, 12969, 12983, 12987, 12995, 13015, 13019, 13031, 13063, 13077, 13103, 13137, 13149, 13173, 13207, 13211, 13227, 13241, 13249, 13255, 13269, 13283, 13285, 13303, 13307, 13321, 13339, 13351, 13377, 13389, 13407, 13417, 13431, 13435, 13447, 13459, 13465, 13477, 13501, 13513, 13531, 13543, 13561, 13581, 13599, 13605, 13617, 13623, 13637, 13647, 13661, 13677, 13683, 13695, 13725, 13729, 13753, 13773, 13781, 13785, 13795, 13801, 13807, 13825, 13835, 13855, 13861, 13871, 13883, 13897, 13905, 13915, 13939, 13941, 13969, 13979, 13981, 13997, 14027, 14035, 14037, 14051, 14063, 14085, 14095, 14107, 14113, 14125, 14137, 14145, 14151, 14163, 14193, 14199, 14219, 14229, 14233, 14243, 14277, 14287, 14289, 14295, 14301, 14305, 14323, 14339, 14341, 14359, 14365, 14375, 14387, 14411, 14425, 14441, 14449, 14499, 14513, 14523, 14537, 14543, 14561, 14579, 14585, 14593, 14599, 14603, 14611, 14641, 14671, 14695, 14701, 14723, 14725, 14743, 14753, 14759, 14765, 14795, 14797, 14803, 14831, 14839, 14845, 14855, 14889, 14895, 14909, 14929, 14941, 14945, 14951, 14963, 14965, 14985, 15033, 15039, 15053, 15059, 15061, 15071, 15077, 15081, 15099, 15121, 15147, 15149, 15157, 15167, 15187, 15193, 15203, 15205, 15215, 15217, 15223, 15243, 15257, 15269, 15273, 15287, 15291, 15313, 15335, 15347, 15359, 15373, 15379, 15381, 15391, 15395, 15397, 15419, 15439, 15453, 15469, 15491, 15503, 15517, 15527, 15531, 15545, 15559, 15593, 15611, 15613, 15619, 15639, 15643, 15649, 15661, 15667, 15669, 15681, 15693, 15717, 15721, 15741, 15745, 15765, 15793, 15799, 15811, 15825, 15835, 15847, 15851, 15865, 15877, 15881, 15887, 15899, 15915, 15935, 15937, 15955, 15973, 15977, 16011, 16035, 16061, 16069, 16087, 16093, 16097, 16121, 16141, 16153, 16159, 16165, 16183, 16189, 16195, 16197, 16201, 16209, 16215, 16225, 16259, 16265, 16273, 16299, 16309, 16355, 16375, 16381],
[16427, 16441, 16467, 16479, 16507, 16553, 16559, 16571, 16573, 16591, 16619, 16627, 16653, 16659, 16699, 16707, 16795, 16797, 16807, 16813, 16821, 16853, 16857, 16881, 16909, 16983, 16993, 17023, 17029, 17053, 17095, 17099, 17101, 17123, 17129, 17135, 17161, 17185, 17215, 17277, 17287, 17301, 17327, 17353, 17387, 17389, 17419, 17475, 17523, 17619, 17621, 17631, 17635, 17659, 17707, 17721, 17753, 17775, 17817, 17823, 17829, 17847, 17861, 17879, 17895, 17907, 17919, 17935, 17949, 17959, 17973, 17991, 18009, 18019, 18033, 18043, 18085, 18117, 18127, 18139, 18225, 18255, 18303, 18343, 18369, 18405, 18409, 18415, 18451, 18457, 18491, 18499, 18523, 18529, 18535, 18559, 18563, 18659, 18717, 18733, 18745, 18793, 18807, 18823, 18857, 18895, 18913, 18997, 19045, 19067, 19073, 19079, 19083, 19107, 19145, 19165, 19193, 19255, 19273, 19291, 19307, 19309, 19315, 19321, 19333, 19351, 19361, 19371, 19385, 19403, 19405, 19413, 19423, 19441, 19451, 19465, 19485, 19519, 19527, 19531, 19541, 19581, 19597, 19621, 19645, 19653, 19665, 19671, 19693, 19743, 19761, 19781, 19791, 19793, 19829, 19855, 19885, 19891, 19905, 19963, 19969, 19989, 20023, 20035, 20041, 20049, 20075, 20077, 20099, 20123, 20179, 20197, 20201, 20207, 20253, 20309, 20319, 20329, 20335, 20383, 20393, 20407, 20411, 20459, 20487, 20511, 20517, 20573, 20641, 20693, 20713, 20781, 20819, 20825, 20831, 20861, 20875, 20889, 20901, 20913, 20945, 20955, 20971, 20973, 20981, 20991, 20997, 21007, 21037, 21093, 21131, 21145, 21155, 21169, 21187, 21189, 21201, 21223, 21285, 21289, 21339, 21403, 21405, 21415, 21433, 21439, 21447, 21489, 21507, 21519, 21527, 21557, 21561, 21575, 21599, 21627, 21645, 21663, 21691, 21725, 21729, 21785, 21807, 21815, 21881, 21887, 21891, 21893, 21905, 21933, 21953, 21971, 21993, 22007, 22029, 22037, 22057, 22063, 22065, 22171, 22187, 22189, 22195, 22209, 22215, 22221, 22263, 22315, 22317, 22335, 22361, 22371, 22397, 22419, 22447, 22461, 22467, 22469, 22487, 22531, 22561, 22579, 22581, 22591, 22593, 22677, 22681, 22691, 22703, 22749, 22759, 22763, 22783, 22863, 22911, 22927, 22935, 22941, 22945, 22951, 22965, 23007, 23017, 23071, 23077, 23099, 23101, 23107, 23109, 23113, 23157, 23221, 23233, 23251, 23253, 23257, 23311, 23319, 23339, 23353, 23395, 23401, 23415, 23449, 23491, 23493, 23521, 23531, 23559, 23563, 23577, 23601, 23625, 23645, 23673, 23683, 23713, 23743, 23745, 23755, 23757, 23781, 23813, 23837, 23859, 23919, 23949, 23957, 23971, 23977, 23995, 24015, 24067, 24079, 24091, 24109, 24135, 24189, 24193, 24217, 24279, 24283, 24295, 24309, 24327, 24345, 24355, 24381, 24387, 24389, 24417, 24427, 24437, 24471, 24543, 24589, 24597, 24623, 24637, 24679, 24683, 24713, 24733, 24747, 24755, 24761, 24789, 24841, 24849, 24877, 24889, 24897, 24957, 24991, 24997, 25007, 25019, 25069, 25077, 25139, 25187, 25199, 25213, 25229, 25247, 25253, 25257, 25271, 25303, 25307, 25309, 25331, 25379, 25393, 25399, 25435, 25453, 25461, 25481, 25489, 25505, 25535, 25583, 25609, 25623, 25665, 25671, 25739, 25759, 25831, 25845, 25857, 25867, 25911, 25915, 25925, 25947, 26001, 26029, 26041, 26047, 26069, 26095, 26103, 26119, 26125, 26147, 26171, 26205, 26219, 26243, 26263, 26279, 26283, 26293, 26329, 26335, 26385, 26395, 26443, 26463, 26473, 26487, 26497, 26531, 26577, 26641, 26653, 26707, 26743, 26771, 26783, 26789, 26793, 26821, 26879, 26905, 26927, 26987, 26995, 27023, 27037, 27041, 27051, 27113, 27137, 27183, 27217, 27227, 27239, 27243, 27245, 27253, 27267, 27287, 27315, 27317, 27327, 27339, 27369, 27375, 27395, 27415, 27435, 27443, 27449, 27463, 27467, 27497, 27517, 27521, 27533, 27575, 27589, 27607, 27617, 27629, 27641, 27695, 27709, 27735, 27763, 27829, 27833, 27841, 27847, 27877, 27913, 27927, 27947, 27987, 28003, 28005, 28009, 28067, 28081, 28091, 28093, 28101, 28169, 28199, 28205, 28211, 28225, 28243, 28283, 28289, 28295, 28309, 28335, 28355, 28379, 28381, 28409, 28417, 28437, 28457, 28465, 28475, 28495, 28503, 28561, 28615, 28633, 28639, 28649, 28677, 28701, 28723, 28797, 28841, 28859, 28873, 28879, 28897, 28947, 28949, 28953, 28977, 28983, 28989, 29035, 29083, 29089, 29109, 29151, 29157, 29175, 29179, 29215, 29233, 29243, 29263, 29287, 29363, 29377, 29389, 29407, 29413, 29425, 29431, 29443, 29449, 29479, 29483, 29581, 29587, 29605, 29629, 29649, 29695, 29715, 29717, 29775, 29787, 29803, 29805, 29867, 29875, 29901, 29919, 29929, 29949, 29979, 29985, 30071, 30075, 30105, 30115, 30141, 30159, 30161, 30187, 30197, 30265, 30279, 30291, 30293, 30303, 30307, 30313, 30367, 30371, 30383, 30417, 30443, 30457, 30475, 30537, 30551, 30573, 30579, 30631, 30645, 30663, 30675, 30677, 30741, 30757, 30769, 30781, 30829, 30923, 30925, 30937, 30959, 30999, 31015, 31053, 31065, 31087, 31089, 31099, 31105, 31111, 31153, 31177, 31191, 31197, 31235, 31259, 31275, 31285, 31295, 31307, 31317, 31361, 31373, 31415, 31419, 31427, 31457, 31477, 31523, 31567, 31569, 31581, 31609, 31631, 31649, 31659, 31673, 31699, 31715, 31729, 31749, 31783, 31789, 31833, 31883, 31891, 31893, 31907, 31927, 31939, 31953, 31993, 31999, 32001, 32021, 32055, 32069, 32115, 32121, 32145, 32151, 32167, 32179, 32199, 32205, 32233, 32251, 32253, 32269, 32281, 32303, 32353, 32373, 32383, 32413, 32427, 32467, 32483, 32485, 32521, 32545, 32575, 32589, 32597, 32625, 32651, 32653, 32671, 32709, 32721, 32743]]
from pyvmodule.tools.polynomial import Polynomial
def alloc_seed(deg,used):
    if deg == 0:return 0
    elif deg < len(seeds):
        seed = seeds[deg][used[deg]]
        used[deg]+=1
        return seed
    else:
        deg1 = deg>>1
        deg2 = deg - deg1
        Poly = Polynomial()
        seed = Poly(seeds[deg1][used[deg1]]) * Poly(seeds[deg2][used[deg2]])
        used[deg1]+=1
        used[deg2]+=1
        return int(seed)
def alloc(*args):
    used = defaultdict(int)
    return tuple([alloc_seed(l,used) for l in lengths] for lengths in args)
